/*
 * @lc app=leetcode.cn id=438 lang=java
 *
 * [438] 找到字符串中所有字母异位词
 */

// @lc code=start

import java.util.ArrayList;
import java.util.List;

class Solution {
    int[] pCount = new int[26];
    int[] sCount = new int[26];
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();

        int sLen = s.length(), pLen = p.length();
        if(sLen < pLen){
            return ans;
        }
        for(int i=0;i<pLen;i++){
            pCount[p.charAt(i) - 'a'] ++;
            sCount[s.charAt(i) - 'a'] ++;
        }

        if(check()){
            ans.add(0);
        }
        for(int i=pLen;i<sLen;i++){
            sCount[s.charAt(i-pLen) - 'a']--;
            sCount[s.charAt(i) - 'a']++;
            if(check()){
                ans.add(i-pLen + 1);
            }
            // System.out.println(s.charAt(i-pLen) + " " + s.substring(i-pLen + 1,i + 1));
        }
        return ans;
    }
    private boolean check(){
        for(int i=0;i<26;i++){
            if(sCount[i] != pCount[i]){
                return false;
            }
        }
        return true;
    }
}
// @lc code=end

